/**
 * 
 */
package com.gwcloud.leetcode.hot100;

/**
 * @ClassName   : Leetcode0033 
 * @author      : ganwei 
 * @date        : 2020年5月13日
 * @Description : Leetcode0033 搜索旋转排序数组
 */
public class Leetcode0033 {
    /**
     * -解题思路，二分查找
     */
	public int search(int[] nums, int target) {
        if(nums.length == 0){
            return -1;
        }
        if(nums.length == 1){
            if(nums[0] == target){
                return 0;
            }else{
                return -1;
            }
        }
		int i = 0;
		while(i<nums.length-1){
			
			if(nums[i] > nums[i+1]){
				break;
			}
			i++;
		}
		if(i == nums.length){
			return search(nums,0,nums.length-1,target);
		}
		if(nums[0] == target){
			return 0;
		}else if(nums[0] > target){
			return search(nums,i+1,nums.length-1,target);
		}else {
			return search(nums,0,i,target);
		}
		
    }
    /**
     * 二分查找
     */
	public int search(int[] nums, int left, int right, int target){
    	
    	while(left <= right){
    		int mid = left + (right - left) / 2;

    		if(nums[mid] == target){
    			return mid;
    		}
    		if(nums[mid] > target){
    			right = mid -1;
    		}else{
    			left = mid + 1;
    		}
    	}
    	return -1;
	}
	
    public static void main(String args[]){
    	Leetcode0033 l0033 = new Leetcode0033();
    	int[] nums = {1,3};
    	int index = l0033.search(nums, 0);
    	System.out.println(index);
    	//System.out.println(2+(3-2)/2);
    }
    
}
